package org.jojo.sort;

/**
 * @author xiexiong
 */
public class ShellSort {
    public  int[] shellSort(int[] arr) {
        int n = arr.length;
        //进行分组，最开始的增量(gap)为数组长度的一半
        for(int gap =n/2;gap>0;gap = gap/2){
            for(int i = gap;i<n;i++){
                //将arr[i]插入到所在分组的正确位置上
                insert(arr,gap,i);
            }
        }
        return arr;
    }

    private void insert(int[] arr, int gap, int i) {
        int inserted = arr[i];
        int j ;
        for(j = i-gap;j>0;j -= gap){
            if(inserted < arr[j]) {
                arr[j + gap] = arr[j];
            }
        }
        arr[j+gap] = inserted;
    }
}
